package com.example.question.dp.dp2;

public class Code02_746 {

    public static void main(String[] args) {
        Code02_746 code = new Code02_746();
//        int i = code.minCostClimbingStairs1(new int[]{1, 100, 1, 1, 1, 100, 1, 1, 100, 1});
        int j = code.minCostClimbingStairs(new int[]{10, 15, 20});
        System.out.println(/*i +*/ " --- " + j);
        System.out.println("code.count = " + code.count);
    }

    /**
     * 这个如何写暴力递归？
     *
     * @param cost
     * @return
     */
    private int count = 0;

    public int minCostClimbingStairs1(int[] cost) {
        int left = dfs(cost, 0, new Integer[cost.length]);
        int right = dfs(cost, 1, new Integer[cost.length]);
        return Math.min(left, right);
    }

    /**
     * 这个如何进行记忆化搜索?
     * 这个又如何改成完全的动态规划呢?
     */
    private int dfs(int[] cost, int startIndex, Integer[] dp) {
        // 边界条件
        if (startIndex == cost.length - 1) {
            return cost[startIndex];
        }
        if (startIndex >= cost.length) {
            return 0;
        }
        if (dp[startIndex] != null) {
            count++;
            return dp[startIndex];
        }
        int minCost = Math.min(dfs(cost, startIndex + 1, dp), dfs(cost, startIndex + 2, dp)) + cost[startIndex];
        // 这个其实就是递推公式
        dp[startIndex] = minCost;
        return dp[startIndex];
    }


    public int minCostClimbingStairs(int[] cost) {
        int minCost = getMinCost(cost, cost.length, cost.length - 1);
        int minCost1 = getMinCost1(cost, cost.length);
        int minCostByDp = getMinCostByDp(cost);
        return minCost1;
    }


    private int getMinCost(int[] cost, int index, int endIndex) {
        if (index == 0 || index == 1) {
            return cost[index];
        }
        int cost1 = getMinCost(cost, index - 1, endIndex);
        int cost2 = getMinCost(cost, index - 2, endIndex);
        return endIndex >= index ? Math.min(cost1, cost2) + cost[index] : Math.min(cost1, cost2);
    }

    public int getMinCostByDp(int[] cost) {
        int len = cost.length;
        int[] dp = new int[len];
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < len; i++) {
            dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
        }
        return Math.min(dp[len - 1], dp[len - 2]);
    }

    /**
     * 这个更符合 递归语义
     */
    private int getMinCost1(int[] cost, int index) {
        if (index == 0 || index == 1) {
            return 0;
        }
        int cost1 = getMinCost1(cost, index - 1);
        int cost2 = getMinCost1(cost, index - 2);
        return Math.min(cost1 + cost[index - 1], cost2 + cost[index - 2]);
    }

    private int getMinCostByDp1(int[] cost) {
        int len = cost.length;
        int[] dp = new int[len + 1];
        dp[0] = dp[1] = 0;
        for (int i = 2; i < len + 1; i++) {
            dp[i] = Math.min(cost[i - 1] + dp[i - 1], cost[i - 2] + dp[i - 2]);
        }
        return dp[len];
    }


    /**
     * 这个解法不行 动态规划要根据 这个递归来写
     */
    public int minCostClimbingStairs2(int[] cost) {
        int[] dp = new int[cost.length + 1];
        dp[cost.length - 1] = cost[cost.length - 1];
        dp[cost.length] = 0;
        for (int i = cost.length - 1; i >= 0; i--) {
            if (i == cost.length - 1) {
                dp[i] = dp[i + 1];
            } else {
                dp[i] = Math.min(dp[i + 1], dp[i + 2]) + cost[i];
            }
        }
        return Math.min(dp[0], dp[1]);
    }


}
